import java.util.Collection; 
import java.util.List; 
import java.util.ArrayList; 
  
/** 
 * CS 1332 Fall 2013 
 * Binary Search Tree 
 *  
 * In this assignment, you will be coding methods to make a functional 
 * binary search tree. If you do this right, you will save a lot of time 
 * in the next two assignments (since they are just augmenting the BST to  
 * make it efficient). Let's get started! 
 *  
 * **************************NOTE************************ 
 * YOU WILL HAVE TO HANDLE NULL DATA IN THIS ASSIGNMENT!! 
 * PLEASE TREAT NULL AS POSITIVE INFINITY!!!! 
 * **************************NOTE************************ 
 *  
 * DO NOT CHANGE ANY OF THE PUBLIC METHOD HEADERS 
 *  
 * Please make any extra inner classes, instance fields, and methods private 
 */
public class BST<T extends Comparable<T>> { 
  
    private Node<T> root; 
    private int size; 
    List<T> list; 
  
    /** 
     * Add data to the binary search tree. Remember to adhere to the BST Invariant: 
     * All data to the left of a node must be smaller and all data to the right of 
     * a node must be larger. Don't forget to update the size.  
     *  
     * For this method, you will need to traverse the tree and find the appropriate 
     * location of the data. Depending on the data's value, you will either explore 
     * the right subtree or the left subtree. When you reach a dead end (you have  
     * reached a null value), simply return a new node with the data that was passed 
     * in. 
     *  
     * PLEASE TREAT NULL DATA AS POSITIVE INFINITY!!!! 
     *  
     * @param data A comparable object to be added to the tree. 
     */
    public void add(T data) { 
        if (root==null)  
            root = new Node<T>(data); 
        else if (data==null || root.getData()!=null && data.compareTo(root.getData())>0) 
            add(root.getRight(),data,root,true); 
        else add(root.getLeft(),data,root,false); 
        size++;} 
  
    private void add(Node<T> node, T data, Node<T> prev, boolean right) { 
  
        if (node==null) { 
            node = new Node<T>(data); 
            if (right)  
                prev.setRight(node); 
            else
                prev.setLeft(node); } 
        else if (data==null || node.getData()!=null && data.compareTo(node.getData())>0) 
            add(node.getRight(),data,node,true);             
        else add(node.getLeft(),data,node,false); } 
  
    /** 
     * Add the contents of the collection to the BST. To do this method, notice that 
     * most every collection in the java collections API implements the iterable  
     * interface. This means that you can iterate through every element in these  
     * structures with a for-each loop. Don't forget to update the size. 
     *  
     * @param collection A collection of data to be added to the tree. 
     */
    public void addAll(Collection<? extends T> c) { 
        for (T item: c) add(item);} 
  
    /** 
     * Remove the data element from the tree. Use the removeChild helper method. 
     *   
     * PLEASE TREAT NULL DATA AS POSITIVE INFINITY! 
     *   
     * @param data The data element to be searched for. 
     * @return retData The data that was removed from the tree. Return null if the 
     * data doesn't exist. 
     */
    public T remove(T data) { 
        if (root==null) return null; 
        if (data.equals(root.getData())) 
            if (root.getLeft()==null && root.getRight()==null)  // no children 
                clear(); 
            else if (root.getLeft()!=null && root.getRight()!=null) 
                root.setData(remove(findMax(root.getLeft()).getData())); 
            else if (root.getLeft()!=null && root.getRight()==null) 
                root = root.getLeft(); 
            else 
                root = root.getRight(); 
        else if (data==null || root.getData()!=null && data.compareTo(root.getData())>0) 
            removeChild(root.getRight(), data, root, true); 
        else removeChild(root.getLeft(), data, root, false); 
          
        return data; 
    } 
  
    /** 
     * This is the hlper method we suggest using, you may code remove in other 
     * ways though. 
     *  
     * There are three cases you have to deal with: 
     * 1. The node to remove has no children 
     * 2. The node to remove has one child 
     * 2. The node to remove has two children 
     *  
     * In the first case, return null. In the second case, return the non-null  
     * child. The third case is where things get interesting. Here, you have two  
     * you will have to find the predecessor and then copy their data  
     * into the node you want to remove. You will also have to fix the 
     * predecessor's children if necessary. Don't forget to update the size. 
     * 
     * @param Node<T> node The node to be removed 
     * @param Node<T> The new child node 
     */
    private boolean removeChild(Node<T> node, T data, Node<T> prev, boolean right) { 
        if (node==null) return false; 
        if (data.equals(node.getData())) 
            if (node.getLeft()==null && node.getRight()==null)  // no children 
                if (right) prev.setRight(null); 
                else prev.setLeft(null); 
            else if (node.getLeft()!=null && node.getRight()!=null) 
                node.setData(remove(findMax(node.getLeft()).getData())); 
            else if (node.getLeft()!=null && node.getRight()==null) 
                if (right) 
                    prev.setRight(node.getLeft()); 
                else
                    prev.setLeft(node.getLeft()); 
            else 
                if (right) 
                    prev.setRight(node.getRight()); 
                else
                    prev.setLeft(node.getRight()); 
        else if (data==null || node.getData()!=null && data.compareTo(node.getData())>0) 
            removeChild(node.getRight(), data, node, true); 
        else removeChild(node.getLeft(), data, node, false); 
              
        return true; 
        } 
  
        private Node<T> findMax(Node<T> node) { 
            if (node.getRight()==null) 
                return node; 
            else return findMax(node.getRight()); 
        } 
  
        /** 
         * Get the data from the tree. 
         *  
         * This method simply returns the data that was stored in the tree. 
         *  
         * TREAT NULL DATA AS POSITIVE INFINITY! 
         *  
         * @param data The datum to search for in the tree. 
         * @return The data that was found in the tree. Return null if the data doesn't 
         * exist. 
         */
        public T get(T data) { 
            if (contains(data)) 
                return data; 
            else 
                return null;  
        } 
  
        /** 
         * See if the tree contains the data. 
         *  
         * TREAT NULL DATA AS POSITIVE INFINITY! 
         *  
         * @param data The data to search for in the tree. 
         * @return Return true if the data is in the tree, false otherwise. 
         */
        public boolean contains(T data) {        
            return contains(root,data); } 
  
        private boolean contains(Node<T> node, T data) { 
            if (node==null) 
                return false; 
            else if (data!=null && data.equals(node.getData())) 
                return true; 
            else if (data==null && node.getData()==null) 
                return true; 
            else if (data==null || node.getData()!=null && data.compareTo(node.getData())>0) 
                return contains(node.getRight(),data);                   
            else 
                return contains(node.getLeft(),data);  
        } 
  
        /** 
         * Linearize the tree using the pre-order traversal. 
         *  
         * @return A list that contains every element in pre-order. 
         */
        public List<T> preOrder() { 
            list = new ArrayList<T>(); 
            preOrder(root,list); 
            return list; 
        } 
  
        private void preOrder(Node<T> node, List<T> list) { 
            if (node==null) return; 
            list.add(node.getData()); 
            preOrder(node.getLeft(),list); 
            preOrder(node.getRight(),list);          
        } 
  
        /** 
         * Linearize the tree using the in-order traversal. 
         *  
         * @return A list that contains every element in-order. 
         */
        public List<T> inOrder() { 
            list = new ArrayList<T>(); 
            inOrder(root,list); 
            return list; 
        } 
  
        private void inOrder(Node<T> node, List<T> list) { 
            if (node==null) return; 
            inOrder(node.getLeft(),list); 
            list.add(node.getData()); 
            inOrder(node.getRight(),list); 
        } 
  
        /** 
         * Linearize the tree using the post-order traversal. 
         *  
         * @return A list that contains every element in post-order. 
         */
        public List<T> postOrder() { 
            list = new ArrayList<T>(); 
            postOrder(root,list); 
            return list; 
        } 
  
        private void postOrder(Node<T> node, List<T> list) { 
            if (node==null) return; 
            postOrder(node.getLeft(),list); 
            postOrder(node.getRight(),list); 
            list.add(node.getData()); 
        } 
  
        /** 
         * Test to see if the tree is empty. 
         *  
         * @return Return true if the tree is empty, false otherwise. 
         */
        public boolean isEmpty() { 
            return size==0; 
        } 
  
        /** 
         *  
         * @return Return the number of elements in the tree. 
         */
        public int size() { 
            return size; 
        } 
  
        /** 
         * Clear the tree. (ie. set root to null and size to 0) 
         */
        public void clear() { 
            size=0; 
            root=null; 
        } 
  
        /** 
         * Clear the existing tree, and rebuilds a unique binary search tree  
         * with the pre-order and post-order traversals that are passed in. 
         * Draw a tree out on paper and generate the appropriate traversals. 
         * See if you can manipulate these lists to generate the same tree. 
         *  
         * TL;DR - at the end of this method, the tree better have the same 
         * pre-order and post-order as what was passed in. 
         *  
         * @param preOrder A list containing the data in a pre-order linearization. 
         * @param postOrder A list containing the data in a post-order linearization. 
         */
        public void reconstruct(List<? extends T> preOrder, List<? extends T> postOrder) { 
            clear(); 
            addAll(preOrder); 
        } 
  
        public Node<T> getRoot() { // added by author 
            return root; } 
  
    } 